◀ Prev · Parts · Full · Next ▶

• In communication complexity, the equality of two strings can be verified to some reliability using log ⁡ ⁡ n {\displaystyle \log n} bits of communication with a randomized protocol. Any deterministic protocol requires Θ Θ ( n ) {\displaystyle \Theta (n)} bits if defending against a strong opponent.cite-ref-26[26]

• The volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time.cite-ref-27[27] Bárány and Füredi showed that no deterministic algorithm can do the same.cite-ref-28[28] This is true unconditionally, i.e. without relying on any complexity-theoretic assumptions, assuming the convex body can be queried only as a black box.

• A more complexity-theoretic example of a place where randomness appears to help is the class IP. IP consists of all languages that can be accepted (with high probability) by a polynomially long interaction between an all-powerful prover and a verifier that implements a BPP algorithm. IP = PSPACE.cite-ref-29[29] However, if it is required that the verifier be deterministic, then IP = NP.

◀ Prev · Parts · Full · Next ▶